const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

// 动态规划
void async function () {
    line = await readline();
    let [n, m] = line.split(' ').map(Number),
        graph = new Array(n + 1).fill(0).map(() => new Array(n + 1).fill(0).map(() => new Array(n + 1).fill(10009)));

    while (m-- > 0) {
        line = await readline();
        let [u, w, v] = line.split(' ').map(Number);
        graph[u][w][0] = v
        graph[w][u][0] = v
    }

    for (let k = 1; k <= n; k++) {
        for (let i = 1; i <= n; i++) {
            for (let j = 1; j <= n; j++) {
                graph[i][j][k] = Math.min(graph[i][j][k-1], graph[i][k][k - 1] + graph[k][j][k - 1])
            }
        }
    }

    line = await readline();
    while (line = await readline()) {
        let [start, end] = line.split(' ').map(Number)
        console.log(graph[start][end][n] === 10009 ? -1 : graph[start][end][n])
    }
}()


// 动态规划+滚动数组
void async function () {
    line = await readline();
    let [n, m] = line.split(' ').map(Number),
        graph = new Array(n + 1).fill(0).map(() => new Array(n + 1).fill(10009));

    while (m-- > 0) {
        line = await readline();
        let [u, w, v] = line.split(' ').map(Number);
        graph[u][w] = v
        graph[w][u] = v
    }

    for (let k = 1; k <= n; k++) {
        for (let i = 1; i <= n; i++) {
            for (let j = 1; j <= n; j++) {
                graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j])
            }
        }
    }

    line = await readline();
    while (line = await readline()) {
        let [start, end] = line.split(' ').map(Number)
        console.log(graph[start][end] === 10009 ? -1 : graph[start][end])
    }
}()




// djkstra算法多次调用
void async function () {
    line = await readline();
    let [n, m] = line.split(' ').map(Number),
        graph = new Array(n + 1).fill(0).map(() => new Array(n + 1).fill(10009));

    while (m-- > 0) {
        line = await readline();
        let [u, w, v] = line.split(' ').map(Number);
        graph[u][w] = v
        graph[w][u] = v
    }

    line = await readline();
    while (line = await readline()) {
        let [start, end] = line.split(' ').map(Number);
        console.log(djkstra(graph, n, start, end))
    }
}()

function djkstra(graph, n, start, end) {
    let minDist = new Array(n + 1).fill(10009),
        visited = new Array(n + 1).fill(false);

    minDist[start] = 0
    for (let i = 1; i < n; i++) {
        let minPath = Number.MAX_VALUE,
            cur = null;

        for (let i = 1; i <= n; i++) {
            if (visited[i] === false && minDist[i] < minPath) {
                minPath = minDist[i]
                cur = i
            }
        }

        visited[cur] = true

        for (let i = 1; i <= n; i++) {
            if (visited[i] === false && minDist[cur] + graph[cur][i] < minDist[i]) {
                minDist[i] = minDist[cur] + graph[cur][i]
            }
        }
    }
    return minDist[end] === 10009 ? -1 : minDist[end]
}
